﻿using System.Collections.Generic;
using Xunit;
using Xunit.Abstractions;

namespace 初级算法.其他
{
    public class 移动零
    {
        /// <summary>
        /// https://leetcode.cn/problems/move-zeroes/
        /// </summary>
        public class Solution
        {
            /// <summary>
            /// 执行用时：228 ms, 在所有 C# 提交中击败了100.00%的用户
            /// 内存消耗：31.9 MB, 在所有 C# 提交中击败了10.99%的用户
            /// </summary>
            /// <param name="nums"></param>
            public void MoveZeroes(int[] nums)
            {
                int j = 0;
                int zeroNum = 0;
                for (int i = 0; i < nums.Length; i++)
                {
                    if (nums[i] == 0) zeroNum++;
                    else
                    {
                        nums[j++] = nums[i];
                    }
                }
                while (zeroNum-- != 0)
                {
                    nums[j++] = 0;
                }
            }

            /// <summary>
            /// 优化版本，不需要再补0，少移动i==j的情况，就少了0.5MB
            /// 执行用时：224  ms, 在所有 C# 提交中击败了100.00%的用户
            /// 内存消耗：31.3 MB, 在所有 C# 提交中击败了100.00%的用户
            /// </summary>
            /// <param name="nums"></param>
            public void MoveZeroes2(int[] nums)
            {
                int j = 0;
                for (int i = 0; i < nums.Length; i++)
                {
                    if (nums[i] != 0)
                    {
                        if (i > j)
                        {
                            nums[j] = nums[i];
                            nums[i] = 0;
                        }
                        j++;
                    }
                }
            }
        }
        ITestOutputHelper output;

        public 移动零(ITestOutputHelper output)
        {
            this.output = output;
        }

        [Fact]
        public void Test1()
        {

            Solution S = new Solution();

            int[] r = new int[] { 0, 1, 0, 3, 12 };
            S.MoveZeroes(r);
            output.WriteLine("" + string.Join(',', r));

            r = new int[] { 0, 1, 0, 3, 12 };
            S.MoveZeroes2(r);
            output.WriteLine("" + string.Join(',', r));

            //r = new int[] { 0, 1, 0, 3, 12 };
            //S.MoveZeroes(r);
            //output.WriteLine("" + string.Join(',', r));
        }
    }
}
